################################################################################
#       Copyright (C) 2010 Michael Yurko <myurko@gmail.com>
#
#This file is part of pyQAP.
#
#pyQAP is free software: you can redistribute it and/or modify
#it under the terms of the GNU General Public License as published by
#the Free Software Foundation, either version 2 of the License, or
#(at your option) any later version.
#
#pyQAP is distributed in the hope that it will be useful,
#but WITHOUT ANY WARRANTY; without even the implied warranty of
#MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#GNU General Public License for more details.
#
#You should have received a copy of the GNU General Public License
#along with pyQAP.  If not, see <http://www.gnu.org/licenses/>.
################################################################################

import numpy as np
import lap
import bound_helpers
'''
Contains bounds for the QAP.
'''

def none(psol,problem):
    """
    The "null" bound.
    
    A bound which always returns negative infinty.
    
    :param psol: the partial soltuion
    :type psol: PSolution
    :param problem: the QAP problem
    :type problem: Problem
    :returns: a lower bound for the given partial solution
    :rtype: float
    
    Examples:
    
    >>> from pyQAP import *
    >>> prob = problems.QAPLIB('jen4')
    >>> psol = classes.PSolution(prob.n,prob)
    >>> none(psol, prob)
    -inf
    >>> prob = problems.QAPLIB('nug12')
    >>> prob = problems.reduced(prob,6)
    >>> solver.solve(prob, bound=bounds.none, verbose = False)
    QAP Solution: [...] Cost: 94.000000 Nodes visited: 1958.000000 Total time: ...
    
    """
    return -float('inf')
    
def bound1(psol,problem):
    """
    A quick, naive bound.
    
    First real bound try. Takes the minimum of each individual
    possible assignments.
    
    :param psol: the partial soltuion
    :type psol: PSolution
    :param problem: the QAP problem
    :type problem: Problem
    :returns: a lower bound for the given partial solution
    :rtype: float
    
    >>> from pyQAP import *
    >>> prob = problems.QAPLIB('jen4')
    >>> psol = classes.PSolution(prob.n,prob)
    >>> bound1(psol, prob)
    0.0
    >>> prob = problems.QAPLIB('nug12')
    >>> prob = problems.reduced(prob,6)
    >>> solver.solve(prob, bound= bounds.bound1, verbose = False)
    QAP Solution: [...] Cost: 94.000000 Nodes visited: 1335.000000 Total time: ...
    
    """
    #unpack vars from problem and psol
    f = problem.f
    d = problem.d
    sol_array = psol.sol
    bound = 0
    #add cost from already set facilities
    for i in xrange(psol.placed):
        #among already placed
        for j in xrange(psol.placed):
            bound += f[i,j]*d[sol_array[i],sol_array[j]]
        #to not yet set
        for j in xrange(psol.placed+1,psol.n):
            minimum = float('inf')
            #try unset locs
            for unused in psol.unplaced:
                if unused:
                    est_cost = f[i,j]*d[sol_array[i],unused]
                    if est_cost < minimum:
                        minimum = est_cost
            bound += minimum
    #add cost from unplaced yet
    for i in xrange(psol.placed+1,psol.n):
        #to already placed
        for j in xrange(psol.placed):
            minimum = float('inf')
            for unused in psol.unplaced:
                if unused:
                    est_cost = f[i,j]*d[unused, sol_array[j]]
                    if est_cost < minimum:
                        minimum = est_cost
            bound += minimum
        #to unplaced yet
        for j in xrange(psol.placed+1,psol.n):
            minimum = float('inf')
            for unused1 in psol.unplaced:
                if unused1:
                    for unused2 in psol.unplaced:
                        if unused2:
                            est_cost = f[i,j]*d[unused1,unused2]
                            if est_cost < minimum:
                                minimum = est_cost
            bound += minimum
    return bound
    
def bazaraa1(psol, problem):
    '''
    A lower bound by Bazaraa.
    
    Returns a lower bound to the given problem with the partial solution psol.
    It uses the bound outlined in "An exact branch-and-bound prodecure for the
    quadratic-assignment problem." It uses the first method of computing C3.
    
    NOTE: This bound is currently defective. It will raise a NotImplementedError
    exception if you attempt to use it.
    
    :param psol: the partial soltuion
    :type psol: PSolution
    :param problem: the QAP problem
    :type problem: Problem
    :returns: a lower bound for the given partial solution
    :rtype: float
    
    Examples:
    
    Does not work.
    '''
    
    raise NotImplementedError("This bound is currently defective. Its use will\
                              will result in wrong results.")
    
    #unpack some vars
    n = problem.n
    p = psol.placed
    a = psol.sol
    f = problem.f
    d = problem.d
    
    #get first part of bound
    c1 = psol.cost(problem)
    print c1
    
    #calculate and add cost of interaction between assigned objects and
    #unassigned objects plus the fized cost of locating the unassigned objects
    #generate cost matrix for LAP
    size = n-p
    c2_lap = np.empty((size, size))
    for i in xrange(p, n):
        for j in xrange(p, n):
            s = 0
            for k in xrange(p):
                s += f[i, k]*d[j, a[k]]
                s += f[k, i]*d[a[k], j]
            c2_lap[i-p, j-p] = s
    
    #solve lap for c2
    c2 = LAPJV.lap(c2_lap)[0]
    
    #calculate c3 using the first method outlined
    #get costs into sorted lists
    f_costs = f[p:n, p:n].copy()
    d_costs = d[p:n, p:n].copy()
    
    #vectorize
    size = np.size(f_costs)
    f_costs.resize((size))
    d_costs.resize((size))
    
    #sort
    f_costs.sort()
    d_costs.sort()
    
    #reverse and take inner product
    d_costs = d_costs[::-1]
    c3 = np.inner(f_costs, d_costs)
    c3 = 0
    #return lower bound as sum of c1, c2, and c3
    return c1+c2+c3
    
def gilmore_lawler(psol, problem):
    '''
    The classic Gilmore-Lawler bound.
    
    Computes the Gilmore-Lawler lower bound with the given problem and partial
    solution. This uses the lap solver in lap which implements the Hungarian 
    algorithm.
    
    :param psol: the partial soltuion
    :type psol: PSolution
    :param problem: the QAP problem
    :type problem: Problem
    :returns: a lower bound for the given partial solution
    :rtype: float
    
    Examples:
    
    >>> from pyQAP import *
    >>> problem = problems.QAPLIB('nug12')
    >>> psol = classes.PSolution(problem.n)
    >>> psol = psol.add_new(2)
    >>> psol = psol.add_new(4)
    >>> psol = psol.add_new(1)
    >>> psol = psol.add_new(6)
    >>> gilmore_lawler(psol, problem)
    632.0
    >>> problem = problems.QAPLIB('had16')
    >>> psol = classes.PSolution(problem.n)
    >>> psol = psol.add_new(2)
    >>> psol = psol.add_new(6)
    >>> psol = psol.add_new(1)
    >>> gilmore_lawler(psol, problem)
    3579.9999999999995
    >>> problem = problems.reduced(problems.QAPLIB('nug12'), 8)
    >>> solver.solve(problem, bound=bounds.gilmore_lawler, verbose = False)
    QAP Solution: [...] Cost: 214.000000 Nodes visited: 1078.000000 Total time: ...
    >>> problem = problems.reduced(problems.QAPLIB('had16'), 8)
    >>> solver.solve(problem, bound=bounds.gilmore_lawler, verbose = False)
    QAP Solution: [...] Cost: 556.000000 Nodes visited: 480.000000 Total time: ...
    >>> problem = problems.reduced(problems.QAPLIB('sko100f'), 8)
    >>> solver.solve(problem, bound=bounds.gilmore_lawler, verbose = False)
    QAP Solution: [...] Cost: 428.000000 Nodes visited: 1085.000000 Total time: ...
    
    '''
    p = bound_helpers.sub_problem(problem, psol)
    cost = bound_helpers.gilmore_lawler_full(p)
    return cost
